package com.yitiao.data_algorithms.leetcode.editor.cn;

import com.sun.org.apache.regexp.internal.RE;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.ListNode;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.TreeNode;

import java.util.Arrays;

class LianXuZiShuZuDeZuiDaHeLcof {
    // 2022-08-31 17:51:25
    public static void main(String[] args) {
        Solution solution = new LianXuZiShuZuDeZuiDaHeLcof().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxSubArray(int[] nums) {
            // 定义状态（定义子问题）
            //dp[i]：表示以 nums[i] 结尾 的 连续 子数组的最大和。
            int[] dp = new int[nums.length];
            dp[0] = nums[0];
            int ans = dp[0];
            for (int i = 1; i < nums.length; i++) {
                dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
                ans = Math.max(ans, dp[i]);
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}